// 草一共有n的重量，两只牛轮流吃草，A牛先吃，B牛后吃
// 每只牛在自己的回合，吃草的重量必须是4的幂，1、4、16、64....
// 谁在自己的回合正好把草吃完谁赢，根据输入的n，返回谁赢
public class EatGrass {

    public static String win1(int n){
        return f(n,"A");
    }

    //参数表示，剩余的草量，cur表示当前是cur这个动物开始吃草
    public static String f(int rest, String cur){
        String enemy = cur.equals("A") ? "B" : "A";
        if(rest  < 5){
            if(rest == 0 || rest == 2){
                return enemy;
            }else {
                return cur;
            }
        }

        int pick = 1; //当前吃多少草
        while(pick <= rest){ //尝试找到一种cur当前吃多少草才能够赢
            //当前cur吃了pick的草，此时enemy就该吃rest-enemy的草
            if(f(rest - pick,enemy).equals(cur)) {
                return cur;
            }
            pick *= 4;
        }

        return enemy;
    }

    public static void main(String[] args) {
        for(int rest = 0; rest <= 100; rest++){
            System.out.println("rest: " + " win: " + win1(rest));
        }
    }
    //打表找出规律答案是BABAA循环

    public static String win2(int n){
        if(n % 5 == 0 || n % 5 == 2){
            return "B";
        }
        return "A";
    }
}
